package pers.vic.basics.algorithm.dp;

/**
 * @author Vic.xu
 * @description: 72. 编辑距离  动态规划
 * <p>
 * 经过前三个题目的洗礼，我差点以为我已经有点入门动态规划了
 * </p>
 * @date: 2020/11/12 0012 14:47
 */
public class A_04_minDistance_leetcode72 {
    /*
    给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
    你可以对一个单词进行如下三种操作：
    插入一个字符
    删除一个字符
    替换一个字符
     */

    /**
     * 将 word1 转换成 word2 所使用的最少操作数 。
     *
     * @see A_03_minPathSum_leetcode64#minPathSum(int[][])
     * 有点蒙， 我要冷静下，感觉还是动态规划， 那还是三步走起：
     * 可以看作是用word2去匹配word1
     * 1. 定义二维数据dp[i][j]:表示worl1[0,i) word2[0,j]的 这一段区间的匹配情况
     * 2.匹配关系
     * a. 当两个位置字符直接相等的时候  word1[i] == word2[j]，不用编辑，则距离不用增加即：dp[i][j] = dp[i-1][j-1]
     * b. 当两个位置字符直接不相等时候  word1[i] != word2[j]，分三种情况，新增|替换|删除
     * b1. 替换：在word1[i]替换为 word2[j]相等的字符,则变成比较上一个位置的问题 +1
     * b2. 删除：删除word1[i]，dp[i-1][j]
     * b3. 新增：在word1[i]后新增一个，则这个时候word2[j] 的前一个字符 dp[i][j-1]， 标识 word2前一个位置的次数和当前位置次数一致
     * 3. 初始值 : dp[0][0] = 0,第一行 第一列初始化
     */
    public static int minDistance(String word1, String word2) {
        word1 = word1 == null ? "" : word1;
        word2 = word2 == null ? "" : word2;
        int m = word1.length();
        int n = word2.length();
        if (m == 0) {
            return n;
        }
        if (n == 0) {
            return m;
        }
        //dp[i][j]存储的是word1[0~m]位置匹配word2[0~n位置]所需要的最小步骤
        int[][] dp = new int[m+1][n+1];
        dp[0][0] = 0;
        //初始化列和行
        for (int i = 1; i <= m; i++) {
            dp[i][0] = dp[i - 1][0] + 1;
        }

        for (int i = 01; i <= n; i++) {
            dp[0][i] = dp[0][i - 1] + 1;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                //word1 i位置和 word2 j位置匹配
                if (word1.charAt(i-1) == word2.charAt(j-1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    //不匹配时候可进行三种操作
                    //直接把word1[i]的字符 修改为word2[j]处的字符
                    int change = dp[i - 1][j - 1];
                    //直接把word1[i]处的字符删除了，则需要word1[i-1]处的字符和 word[j]处的字符匹配
                    int delete = dp[i - 1][j];
                    //新增：在word1[i]后新增一个和word2[i]相同的字符，则需要word1[i+1]处的字符和word2[j]处的字符匹配，也即word1[i]和word2[j-1]匹配
                    int insert = dp[i][j - 1];
                    //不管做什么操作，都要加一个 1
                    dp[i][j] = 1 + Math.min(Math.min(change, delete), insert);

                }
            }
        }

        return dp[m][n];
    }

    public static void main(String[] args) {
        /*
        3
        horse -> rorse (将 'h' 替换为 'r')
         rorse -> rose (删除 'r')
         rose -> ros (删除 'e')
         */
        System.out.println(minDistance("horse", "ros"));
    }
}
